package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-30
 */

/**
 * 给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。
 */
public class leetcode498 {
    //在同一条斜线上的点 x+y值相等 (0,2)->(1,1)->(2,0)
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return new int[0];

        int m = matrix.length;
        int n = matrix[0].length;
        int[] nums = new int[m * n]; //保存结果

        int k = 0;
        boolean bXFlag = true;  //向右上角遍历为true，向左下角遍历为false
        for (int i = 0; i < m + n; i++){
            int pm = bXFlag ? m : n;  //x的上限
            int pn = bXFlag ? n : m;  //y的上限
            //当初始值超过 x 的上限时，不足的部分加到 y 上面
            int x = (i < pm) ? i : pm - 1;
            int y = i - x;

            while (x >= 0 && y < pn){
                nums[k++] = bXFlag ? matrix[x][y] : matrix[y][x];
                x--;
                y++;
            }

            bXFlag = !bXFlag;
        }

        return nums;
    }
}
